The present invention relates generally to communication protocols, and more specifically to a system for restoring lost or damaged data blocks within a multicast data transmission.
When a transmitting device sends data over various specific routes to multiple receiving devices, different data may be lost across the different routes, potentially resulting in the need to retransmit significant portions of the originally transmitted data. Such is the case for multicast transmissions, in which a single transmitter sends data to potentially thousands of receivers using one or more multicast destination addresses. In order to provide reliable communications, however, a system must be employed to efficiently enable receiving devices to obtain a correct copy of all transmitted information, even in the face of data loss within an underlying communication channel.
Existing systems have used various specific schemes to provide reliable delivery of data through multicast channels. One commonly used approach is known as Automatic Repeat Request (ARQ). In an ARQ based system, all data lost by at least one receiver is retransmitted to all receivers. Accordingly, ARQ based systems may require a large number of packets to be retransmitted even for relatively small loss rates in the individual communication channels.
Other existing multicast systems have attempted to provide error correction in a way that may reduce the total amount of retransmitted data. These existing approaches have operated based on the data lost by the receiving device having the worst case data loss, i.e. the receiver experiencing the highest loss rate. Such techniques include those based on Reed-Solomon codes, which are block-based error correcting codes. While generally effective, Reed-Solomon code correction systems require significant amounts of CPU power. In an application in which large amounts of data must be reliably transferred over a potentially lossy channel, such CPU overhead may easily become prohibitively expensive. Such existing systems also include what is generally referred to as the “Tornado codes” approach, which involves applying exclusive-OR (XOR) operations across randomly selected data subsets to generate error correction data. The Tornado codes approach is relatively fast in terms of computations, and may be used with relatively large sets of data. However, some Tornado codes based solutions are proprietary, and may not be available for use in all instances.
It would therefore be desirable to have a system for providing reliable data transmission in a multicast communication environment which does not base its data correction on loss estimates or previous measurements of data loss. The system should further require fewer computational resources than is needed by Reed-Solomon systems, and limit the amount of data that must be transmitted in the face of data loss.